#pragma warning(disable : 4996)
#include<stdlib.h>
struct Node {
    int val;
    struct Node* next;
    struct Node* random;

};
struct Node* Add()
{
    struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
    newnode->next = NULL;
    newnode->random = NULL;
    newnode->val = 0;
    return newnode;
}
struct Node* AddNode(struct Node* head)
{
    struct Node* list2 = Add();
    list2->val = head->val;
    struct Node* tail = list2;
    head = head->next;
    while (head)
    {
        list2->next = Add();
        list2 = list2->next;
        list2->val = head->val;
        head = head->next;
    }
    return tail;

}
struct Node* copyRandomList(struct Node* head) {
    if (head == NULL)
    {
        return NULL;
    }
    struct Node* list1 = head;
    struct Node* list2 = AddNode(head);
    struct Node* hhead = head;
    struct Node* tail = list2;
    int count = 0;
    while (list1)
    {
        count = 0;
        hhead = head;
        struct Node* des = list1->random;
        while (hhead != des)
        {
            hhead = hhead->next;
            count++;
        }
        des = list2;
        while (count--)
        {
            des = des->next;
        }
        tail->random = des;
        tail = tail->next;
        list1 = list1->next;
    }
    return list2;


}


int main()
{
    struct Node*n1= (struct Node*)malloc(sizeof(struct Node));
    struct Node*n2 = (struct Node*)malloc(sizeof(struct Node));
    n1->next = n2;
    n1->random = n1;
    n1->val = 1;
    n2->next = NULL;
    n2->random = n1;
    n2->val = 2;
    n1 = copyRandomList(n1);
    

	return 0;
}